package com.c2b.algorithm.leetcode.hot100;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author c2b
 * @since 2023/4/21 17:26
 */
public class Hot617MergeTrees_S {

    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return root1 != null ? root1 : root2;
        }
        final TreeNode merged = new TreeNode(root1.val + root2.val);
        merged.left = mergeTrees(root1.left, root2.left);
        merged.right = mergeTrees(root1.right, root2.right);
        return merged;
    }

    public TreeNode mergeTrees2(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return root1 != null ? root1 : root2;
        }
        // 合并后的节点
        TreeNode merged = new TreeNode(root1.val + root2.val);
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue.offer(merged);
        queue1.offer(root1);
        queue2.offer(root2);
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode mergeNode = queue.poll();
            TreeNode curr1Node = queue1.poll();
            TreeNode curr2Node = queue2.poll();
            TreeNode curr1NodeLeft = curr1Node.left;
            TreeNode curr1NodeRight = curr1Node.right;
            TreeNode curr2NodeLeft = curr2Node.left;
            TreeNode curr2NodeRight = curr2Node.right;

            if (curr1NodeLeft != null || curr2NodeLeft != null) {
                if (curr1NodeLeft != null && curr2NodeLeft != null) {
                    // 两棵树的左子节点都不为null，合并值，继续向下搜索
                    TreeNode left = new TreeNode(curr1NodeLeft.val + curr2NodeLeft.val);
                    mergeNode.left = left;
                    queue.offer(left);
                    queue1.offer(curr1NodeLeft);
                    queue2.offer(curr2NodeLeft);
                } else {
                    // 如果有其中一棵树的左子节点为null，让另一棵树的左子节点成为合并树的左子节点
                    mergeNode.left = curr1NodeLeft != null ? curr1NodeLeft : curr2NodeLeft;
                }
            }

            if (curr1NodeRight != null || curr2NodeRight != null) {
                if (curr1NodeRight != null && curr2NodeRight != null) {
                    // 两棵树的右子节点都不为null，合并值，继续向下搜索
                    TreeNode right = new TreeNode(curr1NodeRight.val + curr2NodeRight.val);
                    mergeNode.right = right;
                    queue.offer(right);
                    queue1.offer(curr1NodeRight);
                    queue2.offer(curr2NodeRight);
                } else {
                    // 如果有其中一棵树的右子节点为null，让另一棵树的右子节点成为合并树的左子节点
                    mergeNode.right = curr1NodeRight != null ? curr1NodeRight : curr2NodeRight;
                }
            }
        }
        return merged;
    }
}
